模拟赛题解/2025.9.5 模拟赛

T1-异或和（xorsum）

题面

给定 $n,p$，求有多少个 $k$ 满足：存在两个非负整数 $x,y$ 使得 $x+y=n$，且 $x\oplus y=k$，其中 $\oplus$ 表示 $p$ 进制不进位加法。

具体来说，若 $x,y$ 在 $p$ 进制下从低到高第 $i$ 位分别为 $a,b$，则 $x\oplus y$ 在 $p$ 进制下从低到高第 $i$ 位为 $(a+b)\bmod p$。

你需要回答 $T$ 次询问。为了减少输出量，记第 $i$ 次询问的答案为 $ans_i$，你只需要输出

$$\left(\sum_{i=1}^Ti\times ans_i\right)\bmod2^{64}$$

$1\leq T\leq 10^6,0\leq n\leq 10^{18},2\leq p\leq 10^{18}$。

题解

法一：数位 dp

先考虑二进制的情况，$\oplus$ 即异或。

若 $x\oplus y=k$，则对于 $k$ 二进制下为 $1$ 的那些位， 在这一位上必然有一个 $0$ 和一个 $1$，对于 $k$ 二进制下为 $0$ 的那些位， 在这一位上可以有两个 $1$ 或两个 $0$。因此记 $l=n-k$，即 $x+y=k+l=n$，要求 $l$ 的第 $i$ 位若为 $1$，则 $k$ 的第 $i-1$ 位必须为 $0$。

或者说容易发现 $x+y=x\oplus y+2(x\&y)=n$，所以 $l=n-k=2(x\&y)$，显然若 $x\&y$ 某位为 $1$ 则 $x\oplus y$ 这一位必须为 $0$。

可以对着这个条件数位 dp，复杂度 $O(T\log n)$，常数较大，期望获得 30~70 分。

对于 $p\not=2$ 的情况，条件是类似的，但是在数位 dp 时无法直接枚举 $k$ 这一位填什么。但是容易根据进位情况唯一确定 $k$，因此仍然可以数位 dp，复杂度 $O(T\log n)$，期望获得 40~100 分。

法二：递推

考虑 $p=2,n\leq 10^6$ 的部分分，如何获得一个快速递推答案的式子。

记 $a_n$ 为 $n$ 的答案，打表或许可以发现 $a_{2n}=a_n+a_{n-1},a_{2n+1}=a_n$。 证明是简单的，显然若 $x+y=2n+1$，则 $x,y$ 最低位必然一个 $1$ 一个 $0$，$x\oplus y=k$ 最低位必然为 $1$，所以可以简单地把最低位删除，递归到 $a_n$。

若 $x+y=2n$，则 $x,y$ 最低位可以两个 $1$ 或两个 $0$，$x\oplus y=k$ 最低位必然为 $0$，因此删除最低位后可以选择递归到 $a_n$ 或 $a_{n-1}$。显然 $n$ 和 $n-1$ 奇偶性不同，所以不会算重。

复杂度 $O(n+T)$，期望获得 30 分。

若 $p\not=2$，可以类似地得到 $a_{pn+(r<p-1)}=a_n+a_{n-1},a_{pn+p-1}=a_n$。

复杂度 $O(n+T)$，期望获得 40 分。

根据递推式，如果想求出两个相邻的 $a$，则只需要求出两个更小的相邻的 $a$ 即可。复杂度 $O(T\log n)$， 期望获得 100 分。

T2-图计数（gracnt）

题面

给定一张 $n$ 个点 $m$ 条边的无向图（可能存在重边自环），第 $i$ 条边连接点 $u_i$ 和 $v_i$，有一个权值 $a_i$ 和一个初始为 $0$ 的计数器 $b_i$。

你可以任选一个起点，沿着图上的边走任意多步，每次经过第 $i$ 条边时，会将 $b_i$ 改为 $b_{i+1}\bmod a_i$。

求这个过程可以生成多少种不同的 $b_1,b_2,\cdots,b_m$，对 $998244353$ 取模。

$1\leq n\leq2\times10^5,0\leq m\leq4\times10^5,1\leq u_i,v_i\leq n,1\leq a_i\leq 998244353$。

题解

显然两个连通块之间是独立的，记第 $i$ 个连通块的答案为 $ans_i$，则最终答案为 $1+\sum_i(ans_i-1)$（注意避免算重 $b_i$ 全为 $0$ 的情况）。接下来只需考虑连通图。

记 $c_i$ 为第 $i$ 条边的实际经过次数，这样一组 $c_i$ 是否合法实际上就是个欧拉路问题，结论是只保留 $c_i$ 的边后，图仍然连通，并且只存在至多两个度数为奇数的点。

显然 $c_i$ 可以任取 $b_i+ka_i$，所以只需将 $c_i$ 加上 $2a_i$，就不会改变度数奇偶性，并且无需考虑图连通的限制。

如果 $a_i$ 是奇数，那么无论 $b_i$ 是多少，都可以通过加上一个 $a_i$ 改变 $c_i$ 的奇偶性，所以此时 $b_i$ 取什么实际上是无所谓的，只需将答案乘上 $a_i$ 即可。可以通过 $a_i=3$ 的部分分。

如果 $a_i$ 是偶数，则 $c_i$ 的奇偶性与 $b_i$ 相同，我们只关注奇偶性，因此可以先将答案乘上 $\frac{a_i}{2}$。

先考虑 $a_i=2$ 的情况。不妨先提取出连通块的一棵生成树，可以说明，任意指定零个或两个度数为奇 数的点，并任意指定非树边的 $b_i$，都唯一存在一组树边的 $b_i$ 使得度数合法。证明也很简单，树的叶子节点可以唯一确定与其相连的边的状态，这样每次剥掉一层叶子即可。

因此，对于一个 $a_i=2$ 的连通块，如果有 $n$ 个点 $m$ 条边，答案为 $(\binom{n}{2}+1)2^{m-n+1}$。可以通过 $a_i=2$ 的部分分。

接下来考虑一个连通块 $a_i$ 既有奇数也有偶数的情况。对于一条 $a_i$ 为奇数的边，可以同时改变连接的两个点的度数奇偶性，可以理解为度数可以沿 $a_i$ 为奇数的边传递。因此直接将 $a_i$ 为奇数的边连接的两个点合并起来即可。

整体算法流程是：将 $a_i$ 为奇数的边缩起来之后，对于每个连通块，统计点数和边数并计算答案。可以 dfs 或者并查集维护。

复杂度 $O(n+m)$。

T3-黑白灰（blwhgr）

题面

数轴上有黑/白/灰三种颜色的点，每种各 $n$ 个。第 $i$ 个黑/白/灰点的坐标为 $x_i/y_i/z_i$，第 $i$ 个灰点有权值 $w_i$。

你可以执行任意次操作，每次操作你可以选择三种颜色的点各一个，记你选择的黑/白/灰点的坐标为 $X/Y/Z$，满足 $X\leq Z\leq Y$，然后将这三个点删除，并得到你选择的灰点的权值。

求你能得到的最大权值和。

$1\leq n\leq 10^5,1\leq x_i,y_i,z_i,w_i\leq 10^9$。

题解

特殊性质都有简单的贪心方式。

可以建出费用流模型：将灰点拆为入点和出点，源点向黑点连边 $(1,0)$，黑点向后面的灰点入点连边 $(1,0)$，灰点入点和出点之间连边 $(1,w)$，灰点出点向后面的白点连边 $1,0$，白点向汇点连边 $(1,0)$。 跑最大费用流即可。

依据建边方式可以通过 $n\leq300$ 或 $n\leq2000$ 的部分分。

根据费用流模型可以得到结论：记进行 $x$ 次操作的最大答案为 $ans_x$，$ans$ 有凸性，因此是单峰的。可以三分操作次数，问题转变为求进行 $x$ 次操作的最大答案。

显然黑点一定选前 $x$ 个，白点一定选后 $x$ 个。考虑黑白点之间的匹配，如果存在交叉，即黑点 $a,b$，白点 $c,d$ 满足 $a$ 匹配 $c$ 且 $b$ 匹配 $d$，且 $x_a<x_b\leq y_d<y_c$，交换匹配关系一定不劣。所以可以认为从前往后第 $i$ 个黑点匹配第 $i$ 个白点。

考虑权值最大的灰点，如果不被任何一组黑白点的匹配覆盖，那么可以直接扔掉不管，否则这个灰点一定会被某次操作选中。证明考虑如果这个点没有被选中，直接将某个覆盖其的黑白匹配选择的灰点修改为这个点即可使答案增加。

这个权值最大的灰点直接贪心选择其左侧第一个黑点和右侧第一个白点即可。注意这可能会破坏我们既定的黑白匹配关系，但是不重要，将黑白点重新按顺序匹配即可。

这样就可以按权值从大到小依次考虑每个灰点并计算答案。容易使用 multiset 或并查集，树状数组等数据结构维护，单次三分复杂度 $O(n\log n)$，总复杂度 $O(n\log^2n)$。

T4-斗恶龙（dragon）

题面

有 $n$ 个恶龙，第 $i$ 个恶龙初始等级为 $a_i$。你要支持 $q$ 次操作：

• 1 l r k，将第 $l\sim r$ 个恶龙中所有等级为 $k-1$ 的恶龙的等级改为 $k$。

• 2 l r k，将第 $l\sim r$ 个恶龙中所有等级为 $k$ 的恶龙的等级改为 $k-1$。

• 3 l r x y，求第 $l\sim r$ 个恶龙中有多少恶龙等级在 $x\sim y$ 之间。

$1\leq n,q\leq5\times10^5,0\leq a_i\leq n,1\leq l\leq r\leq n,1\leq k\leq n,0\leq x\leq y\leq n$。

题解

如果没有修改，查询是普通二维数点，可以维护一棵主席树，版本 $x$ 维护了所有等级 $\leq x$ 的点。

对于修改 1 l r x，将版本 $x-1$ 的区间 $l\sim r$ 直接替换为版本 $x-2$ 的即可。对于修改 2 l r x，将版本 $x-1$ 的区间 $l\sim r$ 直接替换为版本 $x$ 的即可。

复杂度 $O((n+q)\log n)$。

对于特殊性质都存在较为简单的维护方法。也有一些根号做法。